#lang lazy

;; ALL TESTS IN A SEPARATE SECTION AT THE BOTTOM OF THE FILE!
;; (to avoid any potential calls to functions before their definitions)

;; -----------------------------------------------------------------------------
;;
;; ************************ UNGRADED DEFINITIONS *******************************
;;
;; -----------------------------------------------------------------------------

(define print-only-errors #t)

(define (test l r)
  (if (equal? l r)
      (if print-only-errors
          (printf "")
          (printf "Test Passed~n"))
      (printf "Test Failed.  Actual: ~S   Expected: ~S~n" l r)))

(define (build-list-of-test-values numerator denominator-from denominator-to)
  (if (> denominator-from denominator-to) 
      empty 
      (cons
       (/ numerator denominator-from) 
       (build-list-of-test-values numerator (+ 1 denominator-from) denominator-to))))

(define (build-list-of-test-values-fast numerator index)
  (if (> (list-ref primes/fast index) (floor (sqrt numerator))) 
      empty 
      (cons 
       (/ numerator (list-ref primes/fast index)) 
       (build-list-of-test-values-fast numerator (+ 1 index)))))

(define (build-vector num f)
  (apply vector (build-list num f)))

;; -----------------------------------------------------------------------------
;;
;; ********************* GRADED DEFINITIONS ***********************************
;;
;; -----------------------------------------------------------------------------

;; Contract: take-while: (any/c . -> . boolean?) (listof any/c) -> (listof any/c)

;; Purpose: Returns the prefix of l such that for all elements p returns true.

;; Definition:
(define (take-while p l)
  (if (empty? l)
      empty 
      (if (not (p (first l)))
          empty
          (cons (first l) (take-while p (rest l))))))

;; -----------------------------------------------------------------------------

;; Contract: build-infinite-list: (exact-nonnegative-integer? . -> . any/c) -> (listof any/c)

;; Purpose: Lazily constructs the infinite list such that (list-ref (build-infinite-list f) i) returns (f i).

;; Definition:
(define (build-infinite-list f)
  (letrec 
      ([r (lambda (n) (cons (f n) (r (+ n 1))))])
    (r 0)))

;; -----------------------------------------------------------------------------

;; Contract: prime? : exact-positive-integer? -> boolean?

;; Purpose: Returns true if n is prime.

;; Definition:
(define (prime? n)
  (if (= n 0)
      #f
      (if (= n 1)
          #f
          (if (= n 2)
              #t 
              (if (empty? 
                   (filter exact-positive-integer? 
                           (build-list-of-test-values n 2 (ceiling (sqrt n)))))
                  #t
                  #f)))))

;; -----------------------------------------------------------------------------

;; Contract: primes : (listof exact-positive-integer?)

;; Purpose: The list of all primes.

;; Definition.  You may find filter, prime?, and build-infinite-list useful.
(define primes
  (filter 
   prime? 
   (build-infinite-list (lambda (n) n))))

;; -----------------------------------------------------------------------------

;; Contract: prime?/fast : exact-positive-integer? -> boolean

;; Purpose: Returns true if n is prime, but tests only prime factors from primes/fast.

;; Definition:
(define (prime?/fast n)
  (if (= n 0)
      #f
      (if (= n 1)
          #f
          (if (= n 2)
              #t 
              (if (empty? 
                   (filter exact-positive-integer? 
                           (build-list-of-test-values-fast n 0)))
                  #t
                  #f)))))

;; -----------------------------------------------------------------------------

;; Contract: primes/fast : (listof exact-positive-integer?)

;; Purpose: The list of all primes constructed with prime?/fast.

;; Definition: 
(define primes/fast
  (filter 
   prime?/fast 
   (build-infinite-list (lambda (n) n))))

;; -----------------------------------------------------------------------------

;; Contract: build-table : (integer integer ((f integer integer) -> any) -> (vector of vectors)

;; Purpose: Takes in number of rows, columns, and a two parameter function and returns a table composed of vectors
;; in which the function has been applied to every cell where the first parameter is the row index and the second
;; parameter is the column index

;; Definition: 
(define (build-table rows cols f)
  (build-vector rows (lambda (x) (build-vector cols (lambda (y) (f x y))))))

;;------------------------------------------------------------------------------

;; Contract: lcs-length : (string string) -> integer

;; Purpose: Takes in two strings and returns the length of the largest common subsequence between the two

;; Definition: 
(define (lcs-length s1 s2)
  (if (or (= (string-length s1) 0) (= (string-length s2) 0))
      0
      (letrec ((table (build-table 
                       (string-length s1) 
                       (string-length s2) 
                       (lambda (x y)
                         (cond
                           [(and (= x 0) (= y 0))
                            (if (eqv? (string-ref s1 x) (string-ref s2 y))
                                1
                                0)]
                           [(= x 0)
                            (if (eqv? (string-ref s1 x) (string-ref s2 y))
                                1
                                (vector-ref (vector-ref table x) (- y 1)))]
                           [(= y 0)
                            (if (eqv? (string-ref s1 x) (string-ref s2 y))
                                1
                                (vector-ref (vector-ref table (- x 1)) y))]
                           [(eqv? (string-ref s1 x) (string-ref s2 y)) (+ (vector-ref (vector-ref table (- x 1)) (- y 1)) 1)]
                           [else (max (vector-ref (vector-ref table x) (- y 1)) (vector-ref (vector-ref table (- x 1)) y))])))))
        (vector-ref (vector-ref table (- (string-length s1) 1)) (- (string-length s2) 1)))))

;; -----------------------------------------------------------------------------
;;
;; ************************* TESTING SECTION ***********************************
;;
;; -----------------------------------------------------------------------------

;; TESTS FOR take-while

(define p (lambda (n) (< n 5)))

;; tests that should return the empty list.
(test (take-while p empty) empty)
(test (take-while p (list 5 2 1)) empty)
(test (take-while p (list 6)) empty)

;; tests that should return a list of arity 1.
(test (take-while p (list 4)) (list 4))
(test (take-while p (list 4 5)) (list 4))
(test (take-while p (list 4 7 10)) (list 4))

;; tests that should return a list of arity 2.
(test (take-while p (list 0 1)) (list 0 1))
(test (take-while p (list 0 1 5)) (list 0 1))
(test (take-while p (list 0 1 7 1)) (list 0 1))

;; tests that should return a list of arity 3.
(test (take-while p (list 0 1 2)) (list 0 1 2))
(test (take-while p (list 0 1 2 5)) (list 0 1 2))
(test (take-while p (list 0 1 2 7 1)) (list 0 1 2))

;; tests that should return a list of arity 4.
(test (take-while (lambda (n) (< n 5)) (list 1 2 3 4 5 1 2)) (list 1 2 3 4))
(test (take-while (lambda (n) (< n 5)) (list 1 2 3 4 10 1 2)) (list 1 2 3 4))

;; -----------------------------------------------------------------------------

;; TESTS FOR build-infinite-list

(define (f i) (+ i 1))
(define il (build-infinite-list f))

(test (list-ref il 0) 1)
(test (list-ref il 1) 2)
(test (list-ref il 2) 3)
(test (list-ref il 3) 4)

(define (f2 i) (+ i 2))
(define i2 (build-infinite-list f2))

(test (list-ref i2 0) 2)
(test (list-ref i2 1) 3)
(test (list-ref i2 2) 4)
(test (list-ref i2 3) 5)

;; -----------------------------------------------------------------------------

;; TESTS FOR prime?

(test (prime? 0) #f)
(test (prime? 1) #f)
(test (prime? 2) #t)
(test (prime? 3) #t)
(test (prime? 4) #f)
(test (prime? 5) #t)
(test (prime? 6) #f)
(test (prime? 7) #t)
(test (prime? 8) #f)
(test (prime? 9) #f)
(test (prime? 10) #f)
(test (prime? 11) #t)
(test (prime? 12) #f)
(test (prime? 13) #t)
(test (prime? 14) #f)
(test (prime? 15) #f)
(test (prime? 16) #f)
(test (prime? 17) #t)
(test (prime? 18) #f)
(test (prime? 19) #t)
(test (prime? 20) #f)
(test (prime? 21) #f)
(test (prime? 22) #f)

;; -----------------------------------------------------------------------------

;; TESTS FOR primes

(test (list-ref primes 0) 2)
(test (list-ref primes 1) 3)
(test (list-ref primes 2) 5)
(test (list-ref primes 3) 7)
(test (list-ref primes 4) 11)
(test (list-ref primes 5) 13)
(test (list-ref primes 6) 17)
(test (list-ref primes 7) 19)
(test (list-ref primes 8) 23)
(test (list-ref primes 9) 29)
(test (list-ref primes 999) 7919)

;; -----------------------------------------------------------------------------

;; TESTS FOR prime?/fast

(test (prime?/fast 0) #f)
(test (prime?/fast 1) #f)
(test (prime?/fast 2) #t)
(test (prime?/fast 3) #t)
(test (prime?/fast 4) #f)
(test (prime?/fast 5) #t)
(test (prime?/fast 6) #f)
(test (prime?/fast 7) #t)
(test (prime?/fast 8) #f)
(test (prime?/fast 9) #f)
(test (prime?/fast 10) #f)
(test (prime?/fast 11) #t)
(test (prime?/fast 12) #f)
(test (prime?/fast 13) #t)
(test (prime?/fast 14) #f)
(test (prime?/fast 15) #f)
(test (prime?/fast 16) #f)
(test (prime?/fast 17) #t)
(test (prime?/fast 18) #f)
(test (prime?/fast 19) #t)
(test (prime?/fast 20) #f)
(test (prime?/fast 21) #f)
(test (prime?/fast 22) #f)

;; -----------------------------------------------------------------------------

;; TESTS FOR primes/fast

(test (list-ref primes/fast 0) 2)
(test (list-ref primes/fast 1) 3)
(test (list-ref primes/fast 2) 5)
(test (list-ref primes/fast 3) 7)
(test (list-ref primes/fast 4) 11)
(test (list-ref primes/fast 5) 13)
(test (list-ref primes/fast 6) 17)
(test (list-ref primes/fast 7) 19)
(test (list-ref primes/fast 8) 23)
(test (list-ref primes/fast 9) 29)
(test (list-ref primes/fast 999) 7919)

;; -----------------------------------------------------------------------------

;; TESTS FOR build-table

(define (multX2ThenAddY x y)                                         
  (+ (* x 2) y))

;Checking square matrix
(define myTable1 (build-table 5 5 multX2ThenAddY))

;checking First Index changes
(test (vector-ref (vector-ref myTable1 0) 0) (multX2ThenAddY 0 0))
(test (vector-ref (vector-ref myTable1 1) 0) (multX2ThenAddY 1 0))
(test (vector-ref (vector-ref myTable1 3) 0) (multX2ThenAddY 3 0))
;Checking Second Index changes
(test (vector-ref (vector-ref myTable1 0) 1) (multX2ThenAddY 0 1))
(test (vector-ref (vector-ref myTable1 0) 2) (multX2ThenAddY 0 2))
(test (vector-ref (vector-ref myTable1 0) 3) (multX2ThenAddY 0 3))
;Checking random indices
(test (vector-ref (vector-ref myTable1 1) 1) (multX2ThenAddY 1 1))
(test (vector-ref (vector-ref myTable1 2) 3) (multX2ThenAddY 2 3))
(test (vector-ref (vector-ref myTable1 4) 1) (multX2ThenAddY 4 1))
(test (vector-ref (vector-ref myTable1 2) 2) (multX2ThenAddY 2 2))
(test (vector-ref (vector-ref myTable1 2) 4) (multX2ThenAddY 2 4))

;Checking Rectangular matrix in 2nd dimension
(define myTable2 (build-table 8 16 multX2ThenAddY))

;checking First Index changes
(test (vector-ref (vector-ref myTable2 0) 0) (multX2ThenAddY 0 0))
(test (vector-ref (vector-ref myTable2 5) 0) (multX2ThenAddY 5 0))
(test (vector-ref (vector-ref myTable2 7) 0) (multX2ThenAddY 7 0))
;Checking Second Index changes
(test (vector-ref (vector-ref myTable2 0) 4) (multX2ThenAddY 0 4))
(test (vector-ref (vector-ref myTable2 0) 9) (multX2ThenAddY 0 9))
(test (vector-ref (vector-ref myTable2 0) 15) (multX2ThenAddY 0 15))
;Checking random indices
(test (vector-ref (vector-ref myTable2 1) 13) (multX2ThenAddY 1 13))
(test (vector-ref (vector-ref myTable2 2) 15) (multX2ThenAddY 2 15))
(test (vector-ref (vector-ref myTable2 4) 2) (multX2ThenAddY 4 2))
(test (vector-ref (vector-ref myTable2 6) 10) (multX2ThenAddY 6 10))
(test (vector-ref (vector-ref myTable2 7) 9) (multX2ThenAddY 7 9))

;Checking Rectangular matrix in 1st dimension
(define myTable3 (build-table 16 8 multX2ThenAddY))

;checking First Index changes
(test (vector-ref (vector-ref myTable3 0) 0) (multX2ThenAddY 0 0))
(test (vector-ref (vector-ref myTable3 8) 0) (multX2ThenAddY 8 0))
(test (vector-ref (vector-ref myTable3 15) 0) (multX2ThenAddY 15 0))
;Checking Second Index changes
(test (vector-ref (vector-ref myTable3 0) 4) (multX2ThenAddY 0 4))
(test (vector-ref (vector-ref myTable3 0) 5) (multX2ThenAddY 0 5))
(test (vector-ref (vector-ref myTable3 0) 6) (multX2ThenAddY 0 6))
;Checking random indices
(test (vector-ref (vector-ref myTable3 13) 1) (multX2ThenAddY 13 1))
(test (vector-ref (vector-ref myTable3 15) 2) (multX2ThenAddY 15 2))
(test (vector-ref (vector-ref myTable3 2) 4) (multX2ThenAddY 2 4))
(test (vector-ref (vector-ref myTable3 10) 6) (multX2ThenAddY 10 6))
(test (vector-ref (vector-ref myTable3 9) 7) (multX2ThenAddY 9 7))

;; -----------------------------------------------------------------------------

;; TESTS FOR lcs-length

;Testing empty string
(define length1a (lcs-length "" "")) ;lcs=
(test length1a 0)
(define length1b (lcs-length "AB" "")) ;lcs=
(test length1b 0)
(define length1c (lcs-length "" "CD")) ;lcs=
(test length1c 0)
;Testing Equivalent Strings
(define length1 (lcs-length "A" "A")) ;lcs=A
(test length1 1)
(define length2 (lcs-length "TEST" "TEST")) ;lcs=TEST
(test length2 4)
(define length3 (lcs-length "LONGER" "LONGER")) ;lcs=LONGER
(test length3 6)
;Testing other strings
(define length4 (lcs-length "ACTGTA" "ACTA")) ;lcs=ACTA
(test length4 4)
(define length5 (lcs-length "DOTAGGY" "DOLLLLLGGY")) ;lcs=DOGGY
(test length5 5)
(define length6 (lcs-length "TICK" "TAICK")) ;lcs=TICK
(test length6 4)
(define length7 (lcs-length "TICK" "FTICK")) ;lcs=TICK
(test length7 4)
(define length8 (lcs-length "NOTHING" "ABCDEF")) ;lcs=
(test length8 0)
(define length9 (lcs-length "BANANA" "LOLALOLNLOLALOLNLOLALOL")) ;lcs=ANANA
(test length9 5)
(define length10 (lcs-length "BHHHHHAHHHHHNHHHHAHHHHHNHHHHAHHHH" "LOLALOLNLOLALOLNLOLALOL")) ;lcs=ANANA
(test length10 5)
(define length11 (lcs-length "ACTA" "AA")) ;lcs=AA
(test length11 2)
(define length12 (lcs-length "CCACTACC" "AA")) ;lcs=AA
(test length12 2)
;Testing string of one character with string of many with multiple matches
(define length13 (lcs-length "A" "ABABABABAB")) ;lcs=A
(test length13 1)
(define length14 (lcs-length "ABABABABAB" "A")) ;lcs=A
(test length14 1)

;; -----------------------------------------------------------------------------
